import re

print 'Example: RSLCS DEIAE GNTRP ATESE SMIDR'
wordinput = raw_input('Word: ')

grid = wordinput.lower().split()
nrows, ncols = len(grid), len(grid[0])

# A dictionary word that could be a solution must use only
# the grid's letters and have length >= 3. (With a case-
# insensitive match)
alphabet = ''.join(set(''.join(grid)))
possible_solution = re.compile('[' + alphabet + ']{3,}$', re.I)

words = set(word.lower()
            for word in open('en_us.dic').read().splitlines()
            if possible_solution.match(word))

prefixes = set(word[:i]
               for word in words
               for i in range(2, len(word)+1))

def neighbors((x, y)):
    for nx in range(max(0, x-1), min(ncols, x+2)):
        for ny in range(max(0, y-1), min(nrows, y+2)):
            yield (nx, ny)

def extending(prefix, path):
    if prefix in words:
        yield (prefix, path)
    for (nx, ny) in neighbors(path[-1]):
        if (nx, ny) not in path:
            prefix1 = prefix + grid[ny][nx]
            if prefix1 in prefixes:
                for result in extending(prefix1, path + ((nx, ny),)):
                    yield result

def solve():
    for y, row in enumerate(grid):
        for x, prefix in enumerate(row):
            for result in extending(prefix, ((x, y),)):
                yield result

# Print a maximal-length word and its path:
#print max(solve(), key=lambda (word, path): len(word))

answers = set([word for (word, path) in solve()])
answers = list(word for word in sorted(answers, key=lambda word: len(word), 
               reverse=True))
#for i in range(100):
#    print answers[i]
for word in answers: print word
